package leetcode.tree;

/**
 * @author wangmaolin1
 * @date 2021/12/26 下午10:57
 */
public class _114二叉树展开为链表 {
    //        if (root==null){
//            return;
//        }
//        TreeNode node=new TreeNode(-1);
//        TreeNode temp=node;
//        preOrder(root, temp);
//        root=null;
//        root=node.right;
    public static void flatten(TreeNode root) {
        //1. base case
        if (root == null) {
            return;
        }
        //2.展开左右子树
        flatten(root.left);
        flatten(root.right);

        //拿到展开后左右子树
        TreeNode left = root.left;
        TreeNode right = root.right;
        //3.左子树清空，然后放在右边
        root.left = null;
        root.right = left;

        //指针遍历到末尾，
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }

    /**
     * 找前缀
     * 对于任意一个节点 node，如果左子树为空，则不做处理，如果不为空，
     * 则它的左子树的最右节点访问后，紧接着会访问 node 的右节点，我们将左子树的最右节点看作前缀节点。
     * 因此，可这么实现：
     * 对于任意节点 node，如果 left=node.left!=null，找到 left 的最右节点，while((temp=left).right!=null){temp=temp.right}
     * 让最右节点的右节点为当前 node 节点的右节点(temp.right=node.right)
     * 然后让当前节点的左子树为空(node.left=null)
     * 当前节点的右子树为其 left 节点(node.right=left)
     * 然后 node=node.right，继续处理下一个节点
     * @param root
     */
    public static void flatten2(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode left = cur.left;
                TreeNode temp = left;
                while (temp.right != null) {
                    temp = temp.right;
                }
                temp.right = cur.right;

                cur.left = null;
                cur.right = left;
            }
            cur = cur.right;


        }
    }


    /*
            1
          2   5
        3  4     6
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);
        flatten(root);
        System.out.println(root);
    }


}
